package top.dprkshow.practice.graph;

import edu.princeton.cs.algs4.Bag;

/**
 * @author Kent HAN
 * @date 2021/9/14
 */
public class Digraph {
    private final int totalVertices;
    private final Bag<Integer>[] adjBagList;

    public Digraph(int totalVertices) {
        this.totalVertices = totalVertices;
        adjBagList = (Bag<Integer> [])new Bag[totalVertices];
        for (int i = 0; i < totalVertices; i++) {
            adjBagList[i] = new Bag<>();
        }
    }

    public void addEdge(int v, int w) {
        adjBagList[v].add(w);
    }

    Digraph reverse() {
        Digraph reversedGraph = new Digraph(totalVertices);
        for (int i = 0; i < totalVertices; i++) {
            for (int j : adj(i)) {
                reversedGraph.addEdge(j,i);
            }
        }
        return reversedGraph;
    }

    Iterable<Integer> adj(int v) {
        return adjBagList[v];
    }

    int getTotalVertices() {
        return totalVertices;
    }
}
